package xyz.xiaotugou.dataStructure.basic;

import java.util.Arrays;
import java.util.Collection;

/**
 * @author ysy
 * @version 1.0
 * @Title: 自定义数组
 *              - 特性；连续内存空间，增删慢、查询快【申请创建数组时，内存管理器会开辟一段连续内存地址】
 *              - 算法时间复杂度：
 *                  - prepend头插：O(1) ~ O(n)
 *                  - append尾插：O(1)
 *                  - lookup随机查询：O(1)
 *                  - insert随机插入：O(n)
 *                  - delete删除：O(n)
 *   todo: 思考System.arraycopy与Arrays.copyOf区别 ??
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.dataStructure.basic
 * <br><b>ClassName:</b> MyArray1
 * <br><b>Date:</b> 2022/1/5 22:22
 */
public class MyArray1<T> {

    /**
     * 数组默认容量
     **/
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * 数组最大容量【抄袭的ArrayList,为VM留一些保留头信息的空间，增加容错】
     **/
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    /**
     * 默认空数组
     **/
    private static final Object[] DEFAULT_EMPTY_ARRAY = {};

    /**
     * 数组
     **/
    transient Object[] element;
    
    /**
     * 数组实际长度
     **/
    private int size;
    
   /**
    * 空构造器
    **/
    public MyArray1() {
        this.element = DEFAULT_EMPTY_ARRAY;
    }

    /**
     * 非空构造器
     *
     * @param capacity 初始容量
     *
     * @throws IllegalArgumentException
     **/
    public MyArray1(int capacity) throws IllegalAccessException {
        if(capacity > 0){
            this.element = new Object[capacity];
        }else if(capacity == 0){
            this.element = DEFAULT_EMPTY_ARRAY;
        }else {
            throw new IllegalAccessException("容量别搞负数啊");
        }
    }

    /**
     * @Author ysy
     * @Description object转化为泛型T
     * @Date 2022/1/9 16:59
     * @Param 
     * @return T
     **/
    public T element(int index){
        return (T)element[index];
    }
    
    /**
     * @Author ysy
     * @Description 前插
     * @Date 2022/1/5 22:33
     * @Param data 待插入的值
     * @return void
     **/
    public void prepend(T data){
        add(data, 0);
    }

    /**
     * @Author ysy
     * @Description 判空
     * @Date 2022/1/9 17:08
     * @Param 
     * @return boolean
     **/
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * @Author ysy
     * @Description 获取size
     * @Date 2022/1/9 17:09
     * @Param
     * @return int
     **/
    public int size(){
        return size;
    }

    /**
     * @Author ysy
     * @Description 后插 【O(1)】
     * @Date 2022/1/5 22:33
     * @Param data 待插入的值
     * @return void
     **/
    public void add(T data){
        // 确保数组容量
        ensureArrayCapacity(size + 1);
        // 赋值到下一个索引位
        element[size++] = data;
    }

    /**
     * @Author ysy
     * @Description 指定位置，插入值
     * @Date 2022/1/5 22:30
     * @Param data 待插入的值
     * @param index 插入的位置(0开始)
     * @return void
     **/
    public void add(T data, int index){
        // 校验index合法性
        checkIndex(index);
        // 确保数组容量
        ensureArrayCapacity(size + 1);
        // 将数组index位置起始的数据后移
        System.arraycopy(element, index, element,index+1, size-index);
        // 赋值到下一个索引位
        element[index] = data;
        size++;
    }
    
    /**
     * @Author ysy
     * @Description 批量后插元素
     * @Date 2022/1/9 17:11
     * @Param 
     * @return void
     **/
    public void addAll(Collection<? extends T> collection){
        Object[] objects = collection.toArray();
        int addLength = objects.length;
        // 数组容量确认
        ensureArrayCapacity(size + addLength);
        // 数组深拷贝
        System.arraycopy(collection, 0, element, size, addLength);
        // 重置size
        size += addLength;
    }

    /**
     * @Author ysy
     * @Description 指定位置，批量添加元素
     * @Date 2022/1/9 17:11
     * @Param
     * @return void
     **/
    public void addAll(int index, Collection<? extends T> collection){
        // 校验index合法性
        checkIndex(index);
        Object[] objects = collection.toArray();
        int addLength = objects.length;
        // 数组容量确认
        ensureArrayCapacity(size + addLength);
        // 数组深拷贝
        System.arraycopy(collection, 0, element, size, size-index);
        // 重置size
        size += addLength;
    }

    /**
     * @Author ysy
     * @Description 校验索引合法性
     * @Date 2022/1/9 17:16
     * @Param
     * @return void
     **/
    private void checkIndex(int index) {
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: " + size);
        }
    }

    /**
     * @Author ysy
     * @Description 获取指定位置的值 【O(1)】
     * @Date 2022/1/5 22:33
     * @Param index 索引
     * @return 查询到的结果
     **/
    public T get(int index){
        // 校验index合法性
        checkIndex(index);
        return element(index);
    }

    /**
     * @Author ysy
     * @Description 修改指定位置的值 【O(1)】
     * @Date 2022/1/9 17:01
     * @Param
     * @return T
     **/
    public T set(int index, T data){
        // 校验index合法性
        checkIndex(index);
        T oldValue = element(index);
        element[index] = data;
        return oldValue;
    }
    
    /**
     * @Author ysy
     * @Description 获取指定值的索引位置
     * @Date 2022/1/9 16:30
     * @Param 
     * @return int
     **/
    public int indexOf(T data){
        // 若检索的值为null，使用==
        if(data == null){
            for(int i = 0; i < size; i++){
                if(element[i] == null){
                    return i;
                }
            }
        } else {
            for (int i=0; i < size; i++){
                if(data.equals(element[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * @Author ysy
     * @Description 从后往前获取指定值的索引位置
     * @Date 2022/1/9 17:05
     * @Param 
     * @return int
     **/
    public int lastIndexOf(T data){
        // 若检索的值为null，使用==
        if(data == null){
            for(int i = size; i > 0; --i){
                if(element[i] == null){
                    return i;
                }
            }
        } else {
            for (int i = size; i > 0; --i){
                if(data.equals(element[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * @Author ysy
     * @Description 删除指定位置的值 【O(n)】
     * @Date 2022/1/5 22:33
     * @Param index 索引
     * @return void
     **/
    public void remove(int index){
        // 校验index合法性
        checkIndex(index);
        // 将index位置之后的所有值前移
        System.arraycopy(element, index+1, element, index, size-index-1);
        // 将最后索引的值置为null
        element[--size] = null;
    }

    /**
     * @Author ysy
     * @Description 删除指定值 【O(n)】
     * @Date 2022/1/9 16:37
     * @Param 
     * @return void
     **/
    public boolean delete(T data){
        // 空值的比较用==
        if(data == null){
            for(int i = 0; i < size; i++){
                if(element[i] == null){
                    remove(i);
                    return true;
                }
            }
        } else {
            // 非空值的比较用equals
            for(int i = 0; i < size; i++){
                if(data.equals(element[i])){
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * @Author ysy
     * @Description 重置数组容量
     * @Date 2022/1/5 22:54
     * @Param 
     * @return void
     **/
    private void ensureArrayCapacity(int minCapacity) {
        // 计算数组所需容量
        int capacity = calculateArrayCapacity(element, minCapacity);
        // 若所需容量不够，则重置数组大小
        if(minCapacity > element.length) {
            resize(minCapacity);
        }
    }

    /**
     * @Author ysy
     * @Description 重置数组大小【按照估计步长扩展】
     * @Date 2022/1/9 16:17
     * @Param 
     * @return void
     **/
    private void resize(int minCapacity) {
        int currentCapacity = element.length;
        // 扩容为原来的1.5倍
        int newCapacity = currentCapacity + (currentCapacity >> 1);
        // 与最小容量比较：小于，则取最小容量
        if(newCapacity < currentCapacity){
            newCapacity = minCapacity;
        }
        // 与最大容量比较：如果超过了，去最大整数，如果OOM就耶了裸，冲~
        if(newCapacity > MAX_CAPACITY){
            newCapacity = Integer.MAX_VALUE;
        }
        // 指定新的容量，并深拷贝到新的数组
        element = Arrays.copyOf(element, newCapacity);
    }

    public void print(){
        for(int i = 0; i<size; i++){
            System.out.print(element[i] + ", ");
        }
        System.out.println();
    }
    /**
     * @Author ysy
     * @Description 计算数组所需的容量大小
     * @Date 2022/1/9 16:11
     * @Param 
     * @return void
     **/
    private static int calculateArrayCapacity(Object[] element, int minCapacity) {
        // 若原为空数组，则取max(所需最小容量, 默认容量)
        if(element == DEFAULT_EMPTY_ARRAY){
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    public static void main(String[] args) throws IllegalAccessException {
        // 添加测试
        MyArray1<Integer> array = new MyArray1<Integer>(10);
        array.add(2);
        array.print();
        array.add(3);
        array.print();
        array.prepend(4);
        array.print();
        array.add(76,1);
        array.print();
        array.add(6);
        array.print();
        array.add(3);
        array.print();
        // 删除测试
        array.remove(2);
        array.print();
        array.delete(78);
        array.print();
        array.remove(1);
        array.print();
        // 查找测试
        int i = array.indexOf(3);
        System.out.println("索引位置：" + i);
        int j = array.lastIndexOf(3);
        System.out.println("索引位置：" + j);
        System.out.println(array.get(0));

    }
}
